# Copyright 2013, Michael H. Goldwasser
#
# Developed for use with the book:
#
#    Data Structures and Algorithms in Python
#    Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
#    John Wiley & Sons, 2013
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

from .hash_map_base import HashMapBase


class ProbeHashMap(HashMapBase):
	"""Hash map implemented with linear probing for collision resolution."""
	_AVAIL = object()  # sentinal marks locations of previous deletions

	def _is_available(self, j):
		"""Return True if index j is available in table."""
		return self._table[j] is None or self._table[j] is ProbeHashMap._AVAIL

	def _find_slot(self, j, k):
		"""Search for key k in bucket at index j.

		Return (success, index) tuple, described as follows:
		If match was found, success is True and index denotes its location.
		If no match found, success is False and index denotes first available slot.
		"""
		firstAvail = None
		while True:
			if self._is_available(j):
				if firstAvail is None:
					firstAvail = j  # mark this as first avail
				if self._table[j] is None:
					return (False, firstAvail)  # search has failed
			elif k == self._table[j]._key:
				return (True, j)  # found a match
			j = (j + 1) % len(self._table)  # keep looking (cyclically)

	def _bucket_getitem(self, j, k):
		found, s = self._find_slot(j, k)
		if not found:
			raise KeyError('Key Error: ' + repr(k))  # no match found
		return self._table[s]._value

	def _bucket_setitem(self, j, k, v):
		found, s = self._find_slot(j, k)
		if not found:
			self._table[s] = self._Item(k, v)  # insert new item
			self._n += 1  # size has increased
		else:
			self._table[s]._value = v  # overwrite existing

	def _bucket_delitem(self, j, k):
		found, s = self._find_slot(j, k)
		if not found:
			raise KeyError('Key Error: ' + repr(k))  # no match found
		self._table[s] = ProbeHashMap._AVAIL  # mark as vacated

	def __iter__(self):
		for j in range(len(self._table)):  # scan entire table
			if not self._is_available(j):
				yield self._table[j]._key
